/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.tree
 * author:David
 * Date:2015年6月16日下午9:20:58
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.search;

import com.xuwei.base.link.Iterator;
import com.xuwei.base.link.LinkedList;
import com.xuwei.base.link.LinkedListDLNode;
import com.xuwei.base.tree.BinTreeNode;

/**
 * 二叉查找树
 * @author David
 * @since 2015年6月16日 下午9:20:58
 * @version 
 * @since JDK 1.6
 */
public class BinSearchTree{

	protected BinTreeNode root;//根结点
	
	protected final static Strategy strategy = new TreeStrategy();
	
	protected BinTreeNode startBN;
	
	
	/*拿到根结点*/
	public BinTreeNode getRoot() {
		return root;
	}

	public BinSearchTree(BinTreeNode root){
		this.root=root;
	}
	
	/**
	 * 查找结点
	 * @param ele
	 * @return
	 */
	public BinTreeNode search(Object ele){
		return binTSearchRe(root, ele);
	}

	//递归算法
	private BinTreeNode binTSearchRe(BinTreeNode rt, Object ele) {
		if(rt==null){
			return null;
		}
		if(strategy.compare(ele, rt.getData())==0){
			return rt;									//等于
		}else if(strategy.compare(ele, rt.getData())==-1){
			return binTSearchRe(rt.getLChild(), ele);   //小于
		}else{
			return binTSearchRe(rt.getRChild(), ele);   //大于
		}
	}
	
	//非递归算法
	private BinTreeNode binTSearch(BinTreeNode rt, Object ele){
		while(rt!=null){
			if(strategy.compare(ele, rt.getData())==0){
				return rt;	           //等于
			}else if(strategy.compare(ele, rt.getData())==-1){
				rt = rt.getLChild();   //小于
			}else{
				rt = rt.getRChild();   //大于
			}
		}
		return null;
	}
	
	/**
	 * 返回以v为根的二叉查找树中最小元素的位置
	 */
	public BinTreeNode min(BinTreeNode v){
		if(v!=null){
			while(v.hasLChild()){
				v = v.getLChild();
			}
		}
		return v;
	}
	
	/**
	 * 返回以v为根的二叉查找树中最大元素的位置
	 */
	public BinTreeNode max(BinTreeNode v){
		if(v!=null){
			while(v.hasRChild()){
				v = v.getRChild();
			}
		}
		return v;
	}
	
	/**
	 * 返回以v为根在中序遍历序列中的后序结点
	 */
	private BinTreeNode getSuccessor(BinTreeNode v){
		if(v==null){
			return null;
		}
		if(v.hasRChild()){
			return (BinTreeNode)min(v.getRChild());
		}
		while(v.isRChild()){
			v = v.getParent();
		}
		return v.getParent();
	}

	/**
	 * 返回以v为根在中序遍历序列中的前驱结点
	 */
	private BinTreeNode getPredecessor(BinTreeNode v){
		if(v==null){
			return null;
		}
		if(v.hasLChild()){
			return (BinTreeNode)max(v.getLChild());
		}
		while(v.isLChild()){
			v = v.getParent();
		}
		return v.getParent();
	}
	
	/**
	 * 在二叉查找树中插入ele
	 * @param ele
	 */
	public void insert(Object ele){
		BinTreeNode p = null;
		BinTreeNode current = root;
		while(current!=null){   //找到待插入位置
			p = current;
			if(strategy.compare(ele, current.getData())==-1){
				current = current.getLChild();
			}else{
				current = current.getRChild();
			}
		}
		startBN = p;       //待平衡出发点
		if(p==null){
			root = new BinTreeNode(ele);//树为空
		}else if(strategy.compare(ele, p.getData())==-1){
			p.setLChild(new BinTreeNode(ele));
		}else{
			p.setRChild(new BinTreeNode(ele));
		}
	}
	
	/**
	 * 在二叉查找树中删除ele
	 * @param ele
	 * @return
	 */
	public Object remove(Object ele){
		BinTreeNode v = (BinTreeNode)binTSearch(root, ele);
		if(v==null){ //查找失败
			return null;
		}
		BinTreeNode del = null; //待删结点
		BinTreeNode subT = null; //待删结点的子树
		if(!v.hasLChild()||!v.hasRChild()){//确定待删结点
			del = v;
		}else{
			del = getPredecessor(v);
			Object old = v.getData();
			v.setData(del.getData());
			del.setData(old);
		}
		startBN = del.getParent();//待平衡出发点
		//此时待删结点只有左子树或右子树
		if(del.hasLChild()){
			subT = del.getLChild();
		}else{
			subT = del.getRChild();
		}
		if(del==root){     //若待删结点为根
			if(subT!=null){
				subT.sever();
			}
			root = subT;
		}
		if(subT!=null){
			//del为非叶子结点
			if(del.isLChild()){
				del.getParent().setLChild(subT);
			}else{
				del.getParent().setRChild(subT);
			}
		}else{//del为叶子结点
			del.sever();
		}
		return del.getData();	
	}
	
	/**
	 * 中序遍历二叉查找树
	 */
	public Iterator inOrderTree(){
		LinkedList list = new LinkedListDLNode();
		return inOrderTreeRe(root, list).elements();
	}

	/**
	 * 中序遍历递归算法
	 */
	private LinkedList inOrderTreeRe(BinTreeNode node, LinkedList list) {
		if(node.hasLChild()){
			inOrderTreeRe(node.getLChild(), list);
		}
		list.insertLast(node);
		if(node.hasRChild()){
			inOrderTreeRe(node.getRChild(), list);
		}
		return list;
	}
	
	
	
}